#include <iostream>
#include <assert.h>
#include <vector>

namespace Y190614_exam_02_3_Reversing_Linked_List {
int main();

typedef int ElementType;

typedef struct LNode* List;
typedef List LPosition;
struct LNode{
	ElementType address;
	ElementType data;
	ElementType next;
};

typedef struct SNode* Stack;
struct SNode {
	LNode* data;
	Stack next;
};

void dump_list2(std::vector<LNode>& rest);
void dump_list(LPosition p, std::vector<LNode>& rest, int N) {
	LPosition p2;
	for (int i = 0; i < N - 1; ++i) {
		p2 = p + 1;
		printf("%05d %d %05d\n", p->address, p->data, p2->address);
		++p;
	}
	if (rest.size() <= 0)
		printf("%05d %d -1\n", p->address, p->data);
	else
		printf("%05d %d %05d\n", p->address, p->data, rest[0].address);
	dump_list2(rest);
}

void dump_list2(std::vector<LNode>& rest) {
	int count = rest.size();
	if (count < 1)
		return;
	LPosition p;
	for (int i = 0; i < count; i++){
		p = &rest[i];
		printf("%05d %d %05d\n", p->address, p->data);
		if (p->next == -1)
			printf("%d\n", p->next);
		else
			printf("%05d\n", p->next);
	}
}

List read_input(int N, std::vector<LNode>& rest) {
	int address, data, next;
	assert(N > 0);
	List values = (List)malloc(N * sizeof(struct LNode));
	LPosition p = values;
	int i = N;
	while (i--) {
		std::cin >> address >> data >> next;
		p->address = address;
		p->data = data;
		p->next = next;
		++p;
	}

	rest.clear();
	while (next != -1) {
		scanf("%d %d %d", &address, &data, &next);
		LNode p;
		p.address = address;
		p.data = data;
		p.next = next;
		rest.push_back(p);
	}

	return values;
}

LPosition list_find(List L, int N, int address) {
	LPosition p = L;
	for (int i = 0; i < N; ++i)
	{
		if (p->address == address)
			return p;
		++p;
	}
	return NULL;
}

List sort_data(List datas, int N, int first) {
	List res = (List)malloc(N * sizeof(struct LNode));
	LPosition p = res;
	LPosition s = NULL;
	while (first != -1) {
		s = list_find(datas, N, first);
		*p = *s;
		++p;
		first = s->next;
	}
	return res;
}

List KN_reverse(List datas, int K, int N) {
	if (K <= 1 || N <= 1)
		return datas;
	int K_2 = K / 2;
	LNode temp;
	
	for (int i = 0; i < N - K + 1; i += K) {
		int m = i + K_2;
		int K1 = i + K - 1;
		for (int j = i; j < m; ++j) {
			temp = datas[j];
			datas[j] = datas[K1 - j];
			datas[K1 - j] = temp;
		}
	}
	return datas;
}

int main()
{
	int first, N, K;

	std::cin >> first >> N >> K;
	std::vector<LNode> rest;
	List values = read_input(N, rest);
	List sorted_values = sort_data(values, N, first);
	std::cout << std::endl;
	dump_list(sorted_values, rest, N);
	KN_reverse(sorted_values, K, N);
	std::cout << std::endl;
	dump_list(sorted_values, rest, N);
	free(values);
	free(sorted_values);
	return 0;
}
}

int main_Y190614_exam_02_3_Reversing_Linked_List()
{
	return Y190614_exam_02_3_Reversing_Linked_List::main();
}